package priv.pront.code.lanqiao.competition.course.date0330;

import java.util.Scanner;

public class 迷宫与陷阱 {
    static int N, K,count = 0;
    static boolean[][] visited;
    static char[][] grid;
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        N = scanner.nextInt();
        K = scanner.nextInt();
        grid = new char[N][N];
        visited = new boolean[N][N];
        for (int i = 0; i < N; i++) {
            grid[i] = scanner.next().toCharArray();
        }
        System.out.println(process(0, 0,0,0));
    }

    private static int process(int curRi, int curCi,int count,int wudi) {
        if (curRi == N - 1 && curCi == N - 1) {
            return count;
        }
//        越界
        if (curRi < 0 || curCi < 0 || curRi == N || curCi == N) {
            return 100000;
        }
//        不越界的情况下走到墙壁了
        if(grid[curRi][curCi] == '#'){
            return 100000;
        }
//        不越界的情况下走到陷阱了
        if(grid[curRi][curCi] == 'X' && wudi == 0){
            return 100000;
        }
//        之前走过这个点重复走
        if(visited[curCi][curRi]){
            return 100000;
        }
//        不越界的情况下踩到无敌道具了
        if(grid[curRi][curCi] == '%'){
            wudi += K;
        }else{
            wudi = Math.max(0, --wudi);
        }
        count++;
        visited[curRi][curCi] = true;
        count += Math.min(Math.min(Math.min(process(curRi + 1, curCi, count, wudi),
                process(curRi, curCi + 1, count, wudi)),
                process(curRi, curCi - 1, count, wudi)),
                process(curRi - 1, curCi, count, wudi)) ;  //已经走过的步数 + 剩下的步数
        return count;

    }

}
